package __sum_closed

import (
	"math"
	"sort"
)
/*
查找到与目标数最接近的三个数之和。
1：先将切片进行排序
2：设置三个指针，首指针，中间的指针，尾指针。
3：首指针从第一个元素开始遍历，到倒数第三个元素，（为什么不到最后一个元素或者倒数第二个元素？因为有中指针和尾指针，所以不能指向倒数第一个和第二个元素）
4：中间的指针，从首指针的下一个元素开始遍历，首指针每向后移动一位，中间的指针就从首指针之后的元素开始。
5：尾指针从末尾的数字开始，向前移动。
6：每次移动指针，计算三个指针所指向数据的和。计算数据总和和目标值的差的绝对值之和。
7：如果绝对值小于先前的差的绝对值，就要记录下来差的绝对值和三个指针指向数据总和。
8：如果总和和目标值相同，直接返回
9：如果总和大于目标值，尾指针向前移动。
10：如果总和小于目标值，中指针向后移动。
 */
func threeSumClosest(nums []int, target int) int {
	n , res , diff := len(nums) , 0 , math.MaxInt32
	sort.Ints(nums)
	if n <= 2 {
		return 0
	}
	for i := 0 ; i < n - 1 ; i ++ {
		for j , k := i + 1 , n - 1 ; j < k ; {
			sum := nums[i] + nums[j] + nums[k]
			if abs(sum - target) < diff {
				res , diff = sum , abs(sum - target)
			}
			if sum == target {
				return res
			} else if sum > target{
				k --
			} else {
				j ++
			}
		}
	}
	return res
}


func abs (a int) int {
	if a < 0 {
		return -a
	}
	return a
}
